package leetcode.editor.vscdev.backtracking;

import java.util.ArrayList;
import java.util.List;

public class lc78 {
    /* 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
    解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 */
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        Solution solution = new Solution();
        List<List<Integer>> subsets = solution.subsets(nums);
        System.out.println(subsets);
    }
}
class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return res;
    }
    // 回溯实现
    private void backtracking(int[] nums, int i){
        // 每次进入下一层时，都把当前节点加入到path中
        res.add(new ArrayList<>(path));
        // 递归结束条件，当遍历完所有节点时，返回上一层
        for (int j = i; j < nums.length; j++) {
            path.add(nums[j]);
            backtracking(nums, j+1);
            path.remove(path.size()-1);
        }

    }
}